The disclosed embodiments of the present invention relate to a link list data structure, and more particularly, to an apparatus and method for using a link-tail of a link list to store a data pattern which is indicative of an end of the link list as well as auxiliary information.
A network switch is a computer networking device that links different network devices. For example, the network switch receives an incoming packet generated from a first network device connected to it, and transmits a modified packet or an unmodified packet derived from the received packet only to a second network device for which the received packet is meant to be received. In general, the received packet is composed of a plurality of data chunks (i.e., a plurality of cell data). Thus, the packet derived from the received packet is also composed of a plurality of data chunks (i.e., a plurality of cell data). The network switch has a packet buffer for buffering data chunks of the derived packet. However, the free storage space available in the packet buffer is not guaranteed to be continuous. As a result, the data chunks of the derived packet may be randomly located in the packet buffer after stored into the packet buffer.
To efficiently manage the data chunks of the derived packet in the packet buffer, a link list may be employed by the network switch. Based on the link list data structure, the link list includes a plurality of nodes concatenated in series, where each node is associated with one of the data chunks of the derived packet in the packet buffer, and has a next node address field used to store an address of a next node. Concerning a link-tail node of the link list, since the link-tail node is the last node of the link list, there is no next node concatenated to the link-tail node. Hence, in a conventional design, the next node address field of the link-tail node would store a null pointer which points to a null address, thereby informing a packet transmitting circuit of the end of the link list when the link list is read by the packet transmitting circuit during the packet transmission. As the link-tail node points to the “null”, the next node address field of the link-tail node is wasted.